Principles of Programming Languages — Appunti TiTilda

Indice

Scheme

Scheme is a minimalist dialect of the Lisp programming language, designed with a focus on simplicity and flexibility.

Scheme is (mostly) a functional programming language: every computation is an expression that evaluates to a value, and there are no statements or commands.

Statements are instructions that perform actions but do not return values, while expressions are constructs that evaluate to produce values.

The syntax of Scheme is characterized by its use of parentheses to denote function application and its uniform treatment of code and data. This type of syntax is known as S-expressions (Symbolic Expressions) and uses prefix (or Polish) notation.

Each expression in Scheme is enclosed in parentheses ((operator arg1 ... argn)), where operator is typically a symbol representing a function or special form, and arg1 to argn are its arguments.

The evaluation order of arguments in an expression is unspecified, meaning that the language does not guarantee a specific order in which the arguments are evaluated, but it ensures that all arguments are evaluated before the procedure is applied.

For example, the mathematical expression 5 + 3 \cdot 2 + z is written in Scheme as:

(+ 5 (* 3 2) z)

It is also possible to use the square brackets [ and ] as parentheses for better readability, especially in nested expressions:

(+ 5 [* 3 2] z)

Scheme is homoiconic, meaning that the code and data share the same representation.

Homoiconicity: The property where the program structure is similar to its data structure. In Lisp dialects, both code and data are represented as S-expressions (nested lists).

In general, most programming languages are not homoiconic to separate code from data, making it easier to reason about programs.

This uniform syntax allows for powerful metaprogramming capabilities, as code can be manipulated as data structures.

Metaprogramming is the practice of writing programs that can generate, manipulate, or analyze other programs or themselves as data.

Variables and Bindings

The scope of variables in Scheme is static (or lexical), meaning that the visibility of a variable is determined by the structure of the code and the location where it is defined.

Scoping can be either static (lexical) or dynamic.

In static scoping, the scope of a variable is determined by the program’s structure (at compile time), while in dynamic scoping, the scope is determined by the program’s execution context (call stack at runtime).

Variable are stored in the heap memory area, which is used for dynamic memory allocation. The heap allows for the creation of variables whose lifetimes are not tied to the function call stack, enabling features like closures.

There is also a Garbage Collector (GC) in Scheme that automatically reclaims memory occupied by objects that are no longer reachable or needed by the program.

When a variable is defined as a constant the value is immutable and the memory area is marked as read-only to prevent accidental modification. This prevents banging operations.

Local Variables

Local variables in Scheme are created using the let keyword, which allows for the binding of values to names.

(let ((x 10)
      (y 20))
  (+ x y)) ; This will evaluate to 30

The let construct creates a new scope where x is bound to 10 and y is bound to 20.

The binding of multiple variable happens in parallel, meaning that the values of the variables cannot depend on each other, inside of the same let expression.

(let ((x 10)
      (y (+ x 5))) ; This will result in an error because x is not yet defined
  (+ x y))
Sequential Bindings

To create sequential bindings, where the value of a variable can depend on previously defined variables, the let* construct is used.

(let* ((x 10)
       (y (+ x 5))) ; This is valid because x is already defined
  (+ x y)) ; This will evaluate to 25
Recursive Bindings

For defining recursive functions or variables that refer to themselves, the letrec construct is used.

(letrec ((factorial
           (lambda (n)
             (if (= n 0)
                 1
                 (* n (factorial (- n 1)))))))
  (factorial 5)) ; This will evaluate to 120

Global Variables

Global variables in Scheme can be defined using the define keyword. These variables are accessible from any part of the program after their definition.

(define pi 3.14159)
(define radius 5)
(* pi (* radius radius)) ; This will evaluate to 78.53975

Sometimes global variables are defined surrounded by * symbols to indicate that they are special or global variables, for example (define *global-var* '()).

Variable Assignment

In Scheme, variables are immutable by default, meaning that once a variable is bound to a value, it cannot be changed.

However, mutable variables can be created using the set! keyword.

(define counter 0)
(set! counter (+ counter 1)) ; This will update the value of counter to 1

The ! operator is called a bang and is used to indicate that a function or operation has side effects, such as modifying a variable or changing the state of the program.

Types

Scheme is a dynamically typed language, meaning that types are associated with values rather than variables. However, it is also strongly typed, as it enforces type safety during runtime operations (e.g., trying to add a number to a string will result in an error).

Scheme supports a variety of data types, including:

Lists

Lists are a fundamental data structure in Scheme, used to represent ordered collections of elements. Lists can contain elements of heterogeneous types, including numbers, strings, symbols, and even other lists.

Lists in Scheme are implemented as linked chains of pairs. Each pair’s car contains an element, and its cdr points to the next pair (or the empty list).

(cons 1 (cons 2 (cons 3 '())))  ; This creates the list (1 2 3)
'(1 . (2 . (3 . ())))           ; Pair notation for the same list
(list 1 2 3)                    ; Procedure calling for the same list
'(1 2 3)                        ; Quoted literal for the same list

The () notation represents the empty list, also known as nil.

By default list are immutable.

Structs

Scheme allows the definition of custom data structures using the struct construct. They are also called records. This enables the creation of new types with named fields. By default, fields are immutable, but is possible to create mutable fields by specifying the #:mutable keyword.

(struct person (
  (name) 
  (age #:mutable)
))

A struct is instantiated by calling it as a procedure:

(define alice (person "Alice" 30))

To access the fields of a struct, accessor procedures are automatically generated:

(person-name alice) ; Returns "Alice"
(person-age alice)  ; Returns 30

To modify a mutable field, a setter procedure is also generated:

(person-age-set! alice 31) ; Updates Alice's age to 31

Structs can also support inheritance by specifying a parent struct:

(struct employee person (
  (employee-id)
))

Records are not classes and do not support methods or encapsulation like in object-oriented programming.

Procedures

In Scheme, procedures (or functions) are first-class citizens, meaning they can be treated like any other data type.

The parameters are passed by value (technically object sharing as objects are not copied in the stack but only the reference to the object is passed), meaning that the actual values of the arguments are passed to the procedure, rather than references to the variables.

Lambda Expressions

Lambda expressions are used to define anonymous functions in Scheme. Anonymous functions are functions that are defined without a name and can be used as arguments to other functions or assigned to variables. They are a fundamental concept in functional programming.

The syntax for a lambda expression is defined by the lambda or λ keyword and is as follows:

(lambda (arg1 arg2 ... argn) body)

Where arg1 to argn are the parameters of the function, and body is the expression that defines the function’s behavior.

For example, the following lambda expression defines a function that takes two arguments and returns their sum:

(lambda (x y) (+ x y))

Defining Named Procedures

Named procedures can be defined using the define keyword.

(define add
  (lambda (x y)
    (+ x y)))

Or using the syntactic sugar for procedure definition:

(define (add x y)
  (+ x y))

To define a procedure with a variable number of arguments (variadic), we can use the dot (.) notation:

(define (sum . numbers)
  (if (null? numbers)
      0
      (+ (car numbers) (apply sum (cdr numbers)))))

String Operations

Scheme provides several built-in procedures for manipulating strings:

Vector Operations

Scheme provides several built-in procedures for manipulating vectors:

List Operations

Scheme provides several built-in procedures for manipulating lists:

Then there are higher-order procedures that operate on lists like:

Syntactic Form

Scheme has some special syntactic forms that are not evaluated in the same way as regular expressions.

Conditional Branching

Conditional branching is used to evaluate different expressions based on certain conditions.

If Expression

The if expression is used for conditional branching in Scheme. In this expression, a condition is evaluated, and based on its truth value, one of two branches is executed, not both.

It has the following syntax:

(if condition then-branch else-branch)

Where condition is an expression that evaluates to a boolean value, then-branch is the expression executed if the condition is true, and else-branch is the expression executed if the condition is false.

When Expression

The when expression is a simplified form of conditional branching that only includes a then-branch. It is used when there is no need for an else-branch.

(when condition then-branch)
Cond Expression

The cond expression is used for multi-way branching, similar to switch or if-else if-else in other languages.

(cond
  (condition1 result1)
  (condition2 result2)
  (else result_else))
Case Expression

The case expression is used for branching based on the value of a single expression. It compares the value against multiple cases and executes the corresponding result for the first matching case.

(case expression
  ((value1 value2 ...) result1)
  ((value3 value4 ...) result2)
  (else result_else))
Unless Expression

The unless expression is the opposite of the when expression. It executes the then-branch only if the condition evaluates to false.

(unless condition then-branch)

Quote

The quote syntactic form is used to prevent the evaluation of an expression. When an expression is quoted, it is treated as a literal value rather than being evaluated.

The syntax for quoting an expression is as follows:

(quote expression)

Alternatively, a shorthand notation using a single apostrophe (') can be used:

'expression

For example, the expression '(1 2 3) represents the list containing the elements 1, 2, and 3 without evaluating it.

Quasiquote

Quasiquote is a syntactic form that allows for partial evaluation of an expression. It is denoted by the backquote character (`). Within a quasiquoted expression, parts of the expression can be evaluated using the comma (,) operator.

For example:

`(1 2 ,(+ 3 4)) ; This will evaluate to the list (1 2 7)
Eval

To evaluate a quoted expression at runtime, the eval function can be used:

(eval '(+ 1 2)) ; Returns 3

Procedural Code Execution

To write procedural code in Scheme, we can use the begin syntactic form, which allows for the sequential execution of multiple expressions.

The syntax for the begin form is as follows:

(begin expression1 expression2 ... expressionN)

Where expression1 to expressionN are the expressions to be executed in sequence. The value of the begin expression is the value of the last expression executed.

Predicates

Predicates are procedures that return a boolean value (#t for true and #f for false).

Type Predicates

Some common predicates in Scheme include checking the type of a value:

Equality Predicates

To compare two values for equality, Scheme provides several predicates:

Logical Operators

The logical operators and, or, and not can be used to combine predicates:

(and (number? x) (> x 0)) ; Checks if x is a positive number
(or (null? lst) (pair? lst)) ; Checks if lst is empty or a pair
(not (string? y)) ; Checks if y is not a string

Custom Predicates

Custom predicates can be defined using lambda expressions or named procedures that should have names ending with a question mark (?):

(define (even? n)
  (= (modulo n 2) 0))

Iteration

Scheme does not have traditional looping constructs like for or while found in imperative programming languages. Instead, iteration is typically achieved through recursion or named let expressions.

Named Let

Named let is a syntactic form that allows for defining recursive functions in a concise manner. The syntax for named let is as follows:

(let label ((param1 init1)
            (param2 init2)
            ...
            (paramN initN))
  body)

Where label is the name of block, param1 to paramN are the parameters with their initial values, and body is the expression that defines the function’s behavior.

To perform iteration, the label needs to be called to perform a goto-like jump to the beginning of the block with updated parameters.

(let label ((n 5))
  (when (>= n 0)
    (displayln n)
    (label (- n 1))))

Tail Recursion

Recursion is a fundamental concept in Scheme and functional programming in general. It involves defining a function that calls itself to solve a problem by breaking it down into smaller subproblems.

A special case of recursion is tail recursion, where the recursive call is the last operation in the function. Tail-recursive functions are optimized by the Scheme interpreter to execute in constant stack space, effectively turning them into iterations.

(define (factorial n acc)
  (if (= n 0)
      acc
      (factorial (- n 1) (* n acc)))) ; Tail call

(factorial 5 1) ; Evaluates to 120

To evaluate memory usage of tail-recursive functions, we can use the trace procedure to monitor function calls:

(require racket/trace) ; Import the trace module
(trace factorial)
(factorial 5 1)

Closure

A closure is a function that captures the lexical scope in which it was defined, allowing it to access variables from that scope even when invoked outside of it. It is made of two components:

(define (make-counter)
  (let ((count 0))
    (lambda ()
      (set! count (+ count 1))
      count)))

(define counter (make-counter))

(counter) ; Returns 1
(counter) ; Returns 2

This allows to create iterators and generators that maintain state across invocations.

The react’s useState hook is an example of closures in action, where the state variable and its updater function are captured within the closure created by the hook.

Macros

Macros in Scheme are a powerful feature that allows programmers to define new syntactic constructs and transformations at compile time. They enable the creation of custom language features by manipulating the code structure before its evaluation. This system is turing complete and allows for advanced metaprogramming techniques that are evaluated at compile time.

Macro definitions use the define-syntax and syntax-rules constructs.

(define-syntax while
  (syntax-rules ()
    ((_ condition body ...)
      (let loop ()
        (when condition
          (begin
            body ...
            (loop))
        ))
    )
  ))

where:

(define-syntax let
  (syntax-rules ()
    ((_ ((var expr) ...) body ...)
      ((lambda (var ...) body ...) expr ...))
  ))

This macro transforms a let expression into an equivalent lambda application, (var expr) ... represent multiple variable bindings.

syntax-rules can also define literals, which are identifiers that must match exactly during macro expansion and are not treated as pattern variables.

(define-syntax my-if
  (syntax-rules (else) ; 'else' is a literal keyword
    ((_ condition then-branch else else-branch)
      (if condition then-branch else-branch))))

In this example, else is a literal—it must appear verbatim in the macro call. If you write (my-if (> x 0) 1 else 2), the else keyword is recognized. Using a different identifier would not match the pattern.

Hygienic Macros

Macros in sceme are hygienic meaning that they prevents unintended variable capture and name collisions during macro expansion. Unlike traditional macros that operate on raw text substitution, hygienic macros maintain the lexical scope of identifiers, ensuring that macro parameters and locally-bound variables don’t inadvertently conflict with variables in the scope where the macro is invoked. This is achieved through automatic renaming of identifiers during expansion, typically by attaching unique tags or timestamps to variable names.

To use global variable, defined at the top level, the name must be surrounded by * symbols, for example (define *global-var* '()).

Continuations

Continuations represent “the rest of the computation” at any given point in a program. They capture what the program will do next, allowing you to pause execution, save that state, and resume it later—possibly multiple times or from different contexts.

In Scheme, continuations are accessed using call/cc (call-with-current-continuation), a procedure that captures the current continuation and passes it to a function as an argument.

Saving Continuations for Later

Continuations become powerful when you save them and invoke them later:

(define saved-k #f)

(+ 1 
  (call/cc
    (lambda (k)
      (set! saved-k k)
      10))) ; Returns 11

(saved-k 20) ; Returns 21

When calling (saved-k 20), you’re saying: “resume the computation from where I captured this continuation, but use 20 instead of 10.” This effectively re-executes (+ 1 20), returning 21.

Early Exit from Loops

A practical use case is breaking out of loops without checking all remaining elements:

(define (search lst target)
  (call/cc
    (lambda (exit)
      (for-each
        (lambda (x)
          (if (= x target)
              (exit x)))
        lst)
      #f)))

(search '(1 2 3 4 5) 3) ; Returns 3

When the target is found, calling exit abandons the rest of the loop and returns the result immediately.

Goto-like jumps

Continuations can also be used to implement goto-like jumps in the code, allowing for non-linear control flow.

(let ([cc (call/cc (lambda (k) (k k)))])
  (set! x (add1 x))
  (if (< x 3)
    (cc cc)   ; Jump back to the beginning
    x
  )
)

Implementation

Continuations can be implemented using two main techniques:

Non-Deterministic Programming

Scheme supports non-deterministic programming through the use of continuations, allowing for the exploration of multiple computation paths.

Using the choose construct, we can define non-deterministic choices in our programs. This construct allows us to specify a set of possible values, and the program can explore different paths based on these choices. This construct stores the current continuation before making a choice, enabling backtracking if needed.

If at any point the we understand that the current computation path is not leading to a valid solution, we can use the fail procedure to backtrack and explore alternative paths. This construct will restore the last saved continuation, removing the current computation state and allowing the program to try a different choice.

(define (is-the-sum-of sum)
  (unless (and (>= sum 0)(<= sum 10))
    (error "out of range" sum))
  (let ((x (choose ’(0 1 2 3 4 5)))
        (y (choose ’(0 1 2 3 4 5))))
    (if (= (+ x y) sum)
      (list x y)
      (fail)
    )
  )
)

This function create two non-deterministic variables x and y. At the beginning they are both 0. When the fail procedure is called, the last continuation is restored, and y becomes 1. If fail is called again, y becomes 2, and so on. When all values for y are exhausted the y choice will fail and x will be incremented to 1, restarting the cycle for y.

Proto-OO

Scheme does not have built-in support for Object Oriented Programming (OOP) like class-based languages (e.g., Java, C++). However, it is possible to implement OOP concepts using various patterns, such as struct-based implementation, message passing, and prototype-based implementation.

Object Oriented Programming (OOP) is a programming paradigm based on the concept of “objects”, which can contain data and code: data in the form of fields (often known as attributes or properties), and code in the form of procedures (often known as methods).

Struct-based Implementation (Records)

Closures allow for data encapsulation as the data can be hidden within the closure’s environment.

By storing lambdas inside a struct (or record), we can create objects where data is hidden within the closure’s environment.

(struct counter (inc dec val))

(define (make-counter)
  (let ((count 0))
    (counter
      (lambda () (set! count (+ count 1))) ; inc
      (lambda () (set! count (- count 1))) ; dec
      (lambda () count))))                 ; val

(define c (make-counter))

((counter-inc c))   ; Increments count
((counter-val c))   ; Returns 1

In this pattern, the “object” is a record of functions, and “methods” are invoked by selecting a field and calling the returned lambda.

Message Passing Implementation

In the message passing pattern, an object is represented as a single procedure (the dispatcher).

This procedure accepts a “message” (usually a symbol) and arguments, then decides which internal logic to execute.

This follows Alan Kay’s original vision of OOP, where communication between objects happens through messages rather than direct method calls.

(define (make-counter)
  (let ((count 0))
    ;; Local methods
    (define (inc)     (set! count (+ count 1)))
    (define (set-val val) (set! count val))
    (define (get-val)     count)
  
    ;; The Dispatcher
    (lambda (message . args)
      (case message
        ((increase) (apply inc args))
        ((set)      (apply set-val args))
        ((value)    (apply get-val args))
        (else (error "Unknown message" message))))))

(define c (make-counter))
(c 'increase) ; Increments
(c 'value)    ; Returns 1
Delegation and Inheritance

Inheritance is achieved by delegation: if the child object doesn’t recognize a message, it passes it to a “parent” object.

(define (make-dec-counter)
  (let ((parent (make-counter)))
    (define (decrease) (parent 'set (sub1 (parent 'value))))
    (define (increase) (parent 'set (add1 (parent 'value))))
  
    (lambda (message . args)
      (case message
        ((decrease) (apply decrease args))        ; new methods
        ((increase) (apply increase args))        ; override parent methods
        (else (apply parent (cons message args))) ; delegate to parent
      )
    )
  )
)

Prototype-based Implementation

In prototype-based OO (like JavaScript or Lua), there are no classes. Objects are cloned from existing prototypes, and behaviors are added or modified dynamically.

Hash tables are typically used to store fields and methods.

(define new-object make-hash)
(define clone      hash-copy)

;; Macros for cleaner syntax
(define-syntax !!
  (syntax-rules ()
    ((_ obj key val)
      (hash-set! obj 'key val))))
(define-syntax ??
  (syntax-rules ()
    ((_ obj key)
      (hash-ref obj 'key))))
(define-syntax ->
  (syntax-rules ()
    ((_ obj msg arg ...)
      ((?? obj msg) obj arg ...))))

(define person (new-object))
(!! person name "Alice")
(!! person greet
    (lambda (self) (string-append "Hi, I'm " (?? self name))))

(-> person greet) ; "Hi, I'm Alice"

The self argument must be passed explicitly to methods to allow access to the object’s local state, mimicking the this pointer.

Inheritance via Prototype Chain

Inheritance is implemented via a dispatch chain: if a property is not found in the current object, the search continues in its parent (prototype).

(define (deep-clone obj)
  (if (not (hash-ref obj '<<parent>> #f))
    (clone obj)
    (let* ((cl (clone obj))
          (par (?? cl <<parent>>)))
      (!! cl <<parent>> (deep-clone par)))))
      
(define (son-of parent)
  (let ((o (new-object)))
    (!! o <<parent>> (deep-clone parent))
    o))

(define (dispatch obj msg)
  (if (eq? obj 'unknown)
    (error "Unknown message" msg)
    (let ((slot (hash-ref obj msg 'unknown)))
      (if (eq? slot 'unknown)
        (dispatch (hash-ref obj '<<parent>> 'unknown) msg)
        slot))))

(define-syntax ??       ;; reader
  (syntax-rules ()
    ((_ obj key)
      (dispatch obj 'key))))
(define-syntax ->        ;; send message
  (syntax-rules ()
    ((_ obj msg arg ...)
      ((dispatch obj 'msg) obj arg ...))))

Error Handling

In scheme errors are raised using the error procedure:

(error "An error occurred")

To define a custom error handling mechanism we must:

Ultima modifica:
Scritto da: Andrea Lunghi